#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;


//class Solution {
//public:
//    int totalFruit(vector<int>& fruits) {
//        int hash[100000] = { 0 };
//        int kid = 0;
//        int length = 0;
//        for (int left = 0, right = 0; right < fruits.size(); right++)
//        {
//            if (hash[fruits[right]] == 0)
//                kid++;
//            hash[fruits[right]]++;
//            while (kid > 2)
//            {
//                hash[fruits[left++]]--;
//                if (hash[fruits[left - 1]] == 0)
//                    kid--;
//            }
//            length = max(length, right - left + 1);
//        }
//        return length;
//    }
//};
//class Solution {
//public:
//    int search(vector<int>& nums, int target) {
//        int left = 0, right = nums.size() - 1;
//        while (left <= right)
//        {
//            int mid = left + (right - left) / 2;
//            if (target > nums[mid])
//            {
//                left = mid + 1;
//            }
//            else if (target < nums[mid])
//            {
//                right = mid - 1;
//            }
//            else
//                return mid;
//        }
//        return -1;
//    }
//};
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        vector<int> ret;
//        int hash1[26] = { 0 };
//        for (int i = 0; i < p.size(); i++)
//        {
//            hash1[p[i] - 'a']++;
//        }
//        int hash2[26] = { 0 };
//        int count = 0;
//        for (int left = 0, right = 0; right < s.size(); right++)
//        {
//            hash2[s[right] - 'a']++;
//            if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
//            {
//                count++;
//            }
//            while (right - left + 1 == p.size())
//            {
//                if (count == p.size())
//                {
//                    ret.push_back(left);
//                }
//                left++;
//                if (hash2[s[left - 1] - 'a'] <= hash1[s[left - 1] - 'a'])
//                {
//                    count--;
//                }
//                hash2[s[left - 1] - 'a']--;
//            }
//
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x) {
//        int sum = 0;
//        for (int i = 0; i < nums.size(); i++)
//            sum += nums[i];
//        int target = sum - x;
//        if (target < 0)return -1;
//        int len = -1;
//        for (int left = 0, right = 0, ret = 0; right < nums.size(); right++)
//        {
//            ret += nums[right];
//            while (ret > target)
//            {
//                ret -= nums[left++];
//            }
//            if (ret == target)
//                len = max(len, right - left + 1);
//        }
//        if (len == -1)
//            return -1;
//        else
//            return nums.size() - len;
//    }
//};
//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        int left = 0, right = 0;
//        int zero = 0, length = 0;
//        int n = nums.size();
//        for (; right < n; right++)
//        {
//            if (nums[right] == 0)zero++;
//            while (zero > k)
//            {
//                left++;
//                if (nums[left - 1] == 0)zero--;
//            }
//            length = max(length, (right - left + 1));
//        }
//        return length;
//    }
//};
//class Solution {
//public:
//    int lengthOfLongestSubstring(string s) {
//        int len = 0;
//        int hash[128] = { 0 }, n = s.size();
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            hash[s[right]]++;
//            while (hash[s[right]] > 1)
//            {
//                hash[s[left]]--;
//                left++;
//
//            }
//            len = max(len, right - left + 1);
//        }
//        return len;
//    }
//};
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int len = INT_MAX;
//        int sum = 0, n = nums.size();
//        for (int left = 0, right = 0; right < n; right++)
//        {
//            sum += nums[right];
//            while (sum >= target)
//            {
//                len = min(len, right - left + 1);
//                sum -= nums[left++];
//            }
//        }
//
//        return len == INT_MAX ? 0 : len;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target) {
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//        int n = nums.size();
//        for (int i = 0; i <= n - 4;)
//        {
//            for (int j = i + 1; j <= n - 3;)
//            {
//                int left = j + 1;
//                int right = n - 1;
//                long long sum = (long)target - nums[i] - nums[j];
//                while (left < right)
//                {
//                    if ((long)nums[left] + nums[right] < sum)left++;
//                    else if ((long)nums[left] + nums[right] > sum)right--;
//                    else
//                    {
//                        ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
//                        left++;
//                        while (left < right && nums[left] == nums[left - 1])left++;
//                        right--;
//                        while (left < right && nums[right] == nums[right + 1])right--;
//                    }
//
//                }
//                j++;
//                while (j <= n - 3 && nums[j] == nums[j - 1])j++;
//            }
//            i++;
//            while (i <= n - 4 && nums[i] == nums[i - 1])i++;
//        }
//        return ret;
//    }
//};
//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) {
//        vector<vector<int>>ret;
//        sort(nums.begin(), nums.end());
//        for (int i = 0; i <= nums.size() - 3;)
//        {
//            int left = i + 1;
//            int right = nums.size() - 1;
//            while (left < right)
//            {
//                int num = nums[left] + nums[right] + nums[i];
//                if (num > 0)
//                {
//                    right--;
//
//                }
//                else if (num < 0)
//                {
//                    left++;
//
//                }
//                else
//                {
//                    ret.push_back({ nums[i],nums[left],nums[right] });
//                    left++;
//                    while (left < right && nums[left] == nums[left - 1])
//                    {
//                        left++;
//                    }
//                    right--;
//                    while (left < right && nums[right] == nums[right + 1])
//                    {
//                        right--;
//                    }
//                }
//            }
//            i++;
//            while (i <= nums.size() - 3 && nums[i] == nums[i - 1])
//            {
//                i++;
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    vector<int> twoSum(vector<int>& price, int target) {
//        int left = 0;
//        int right = price.size() - 1;
//        while (left < right)
//        {
//            if (price[left] + price[right] > target)
//            {
//                right--;
//            }
//            else if (price[left] + price[right] < target)
//            {
//                left++;
//            }
//            else
//            {
//                return { price[left],price[right] };
//            }
//        }
//        return { -1,-1 };
//    }
//};
//class Solution {
//public:
//    int maxArea(vector<int>& height) {
//        int left = 0, right = height.size() - 1;
//        int ret = 0;
//        while (left != right)
//        {
//            int tmp = (right - left) * min(height[right], height[left]);
//            ret = tmp > ret ? tmp : ret;
//            if (height[left] < height[right])
//            {
//                left++;
//            }
//            else
//            {
//                right--;
//            }
//        }
//        return ret;
//    }
//};
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ret = 0;
        for (int i = nums.size() - 1; i >= 2; i--)
        {
            int left = 0, right = i - 1;
            while (left != right)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};
int bitsum(int num)
{
    int result = 0;
    while (num)
    {
        result += pow((num % 10), 2);
        num /= 10;
    }
    return result;
}
bool isHappy(int n) {
    int fast = bitsum(n);
    int slow = n;

    while (fast != slow)
    {
        slow = bitsum(slow);
        fast = bitsum(bitsum(fast));
    }
    return slow == 1;
}
void duplicateZeros(int* arr, int arrSize) {
    int cur = 0;
    int dest = -1;
    while (cur < arrSize)
    {
        if (arr[cur])
            dest++;
        else
            dest += 2;


        if (dest >= arrSize - 1)
            break;
        cur++;
    }

    if (dest == arrSize)
    {
        arr[arrSize - 1] = 0;
        dest -= 2;
        cur--;
    }

    while (cur >= 0)
    {
        if (arr[cur])
        {
            arr[dest--] = arr[cur];
        }
        else
        {
            arr[dest--] = 0;
            arr[dest--] = 0;
        }
        cur--;
    }
}
void Swap(int* n1, int* n2)
{
    int tmp = *n1;
    *n1 = *n2;
    *n2 = tmp;
}
void moveZeroes(int* nums, int numsSize) {
    int dest = -1;
    int cur = 0;
    while (cur <= numsSize - 1)
    {
        if (nums[cur] == 0)
        {
            cur++;
        }
        else
        {
            Swap(&nums[dest + 1], &nums[cur]);
            dest++;
            cur++;
        }
    }
}
//class Solution {
//public:
//    int firstUniqChar(string s) {
//        int hash[26] = { 0 };
//        for (auto e : s) {
//            hash[e - 'a']++;
//        }
//        for (int i = 0; i < s.size(); i++) {
//            if (hash[s[i] - 'a'] == 1)return i;
//        }
//        return -1;
//    }
//};
//class Solution {
//public:
//    vector<string> uncommonFromSentences(string s1, string s2) {
//        vector<string>v;
//        unordered_map<string, int>hash1;
//        unordered_map<string, int>hash2;
//        int i = 0;
//        int j = 0;
//        while (i < s1.size()) {
//            if (s1[i] == ' ') {
//                string tmp = s1.substr(j, i - j);
//                hash1[tmp]++;
//                j = i + 1;
//                i++;
//            }
//            else {
//                i++;
//            }
//        }
//        string tmp = s1.substr(j, i - j + 1);
//        hash1[tmp]++;
//        i = j = 0;
//        while (i < s2.size()) {
//            if (s2[i] == ' ') {
//                string tmp = s2.substr(j, i - j);
//                hash2[tmp]++;
//                i++;
//                j = i;
//            }
//            else {
//                i++;
//            }
//        }
//        tmp = s2.substr(j, i - j + 1);
//        hash2[tmp]++;
//
//        for (auto& e : hash1) {
//            if (hash1[e.first] == 1 && hash2.count(e.first) == 0)v.push_back(e.first);
//        }
//        for (auto& e : hash2) {
//            if (hash2[e.first] == 1 && hash1.count(e.first) == 0)v.push_back(e.first);
//        }
//        return v;
//    }
//};
//class Solution {
//public:
//    bool containsDuplicate(vector<int>& nums) {
//        unordered_map<int, int>hash;
//        for (auto e : nums) {
//            hash[e]++;
//            if (hash[e] >= 2)return true;
//        }
//        return false;
//    }
//};
//class Solution {
//public:
//    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//        multiset<int>hash1;
//        multiset<int>hash2;
//        for (auto e : nums1) {
//            hash1.insert(e);
//        }
//        for (auto e : nums2) {
//            hash2.insert(e);
//        }
//        vector<int>v;
//        multiset<int>::iterator it1 = hash1.begin();
//        multiset<int>::iterator it2 = hash2.begin();
//        while (it1 != hash1.end() && it2 != hash2.end()) {
//            if (*it1 == *it2) {
//                v.push_back(*it1);
//                ++it1;
//                ++it2;
//            }
//            else if (*it1 < *it2) {
//                ++it1;
//            }
//            else ++it2;
//        }
//        return v;
//    }
//};
//class Solution {
//public:
//    int repeatedNTimes(vector<int>& nums) {
//        int N = nums.size();
//        unordered_map<int, int>hash;
//        for (auto e : nums) {
//            hash[e]++;
//            if (hash[e] == N / 2)return e;
//        }
//        return -1;
//    }
//};
//class Solution {
//public:
//    struct cmp {
//        bool operator()(const pair<string, int>& p1, const pair<string, int>& p2) {
//            return p1.second > p2.second
//                || p1.second == p2.second && p1.first < p2.first;
//        }
//    };
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        map<string, int>dict;
//        for (auto& e : words) {
//            dict[e]++;
//        }
//        vector<pair<string, int>>kvV(dict.begin(), dict.end());
//        sort(kvV.begin(), kvV.end(), cmp());
//        vector<string>v;
//        for (int i = 0; i < k; i++) {
//            v.push_back(kvV[i].first);
//        }
//        return v;
//    }
//};
//class Solution {
//public:
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//        sort(nums1.begin(), nums1.end());
//        sort(nums2.begin(), nums2.end());
//        int n1 = nums1.size();
//        int n2 = nums2.size();
//        int i = 0, j = 0;
//        vector<int>v;
//        while (i < n1 && j < n2) {
//            if (nums1[i] == nums2[j]) {
//                if (v.size() == 0 || nums1[i] != v.back()) {
//                    v.push_back(nums1[i]);
//                }
//                i++;
//                j++;
//            }
//            else if (nums1[i] < nums2[j])i++;
//            else j++;
//        }
//        return v;
//    }
//};
//class Solution {
//public:
//    vector<int> postorderTraversal(TreeNode* root) {
//        TreeNode* cur = root;
//        TreeNode* prev = nullptr;
//        vector<int>v;
//        stack<TreeNode*>s;
//        while (cur || !s.empty()) {
//            while (cur) {
//                s.push(cur);
//                cur = cur->left;
//            }
//            TreeNode* top = s.top();
//            if (top->right == nullptr || top->right == prev) {
//                v.push_back(top->val);
//                prev = top;
//                s.pop();
//            }
//            else {
//                cur = top->right;
//            }
//        }
//        return v;
//    }
//};
//class Solution {
//public:
//    vector<int> inorderTraversal(TreeNode* root) {
//        vector<int>v;
//        stack<TreeNode*>s;
//        TreeNode* cur = root;
//        while (cur || !s.empty()) {
//            while (cur) {
//                s.push(cur);
//                cur = cur->left;
//            }
//            TreeNode* top = s.top();
//            s.pop();
//            v.push_back(top->val);
//            cur = top->right;
//        }
//        return v;
//    }
//};
//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        vector<int>v;
//        stack<TreeNode*>s;
//        TreeNode* cur = root;
//        while (cur || !s.empty()) {
//            while (cur) {
//                v.push_back(cur->val);
//                s.push(cur);
//                cur = cur->left;
//            }
//            TreeNode* top = s.top();
//            s.pop();
//            cur = top->right;
//        }
//        return v;
//    }
//};
class Solution {
public:
    unordered_map<int, int>hash;
    TreeNode* _build(vector<int>& inorder, vector<int>& postorder, int& prei, int inbegin, int inend) {
        if (inbegin > inend)return nullptr;
        TreeNode* root = new TreeNode(postorder[prei]);
        int tmp = postorder[prei];
        root->right = _build(inorder, postorder, --prei, hash[tmp] + 1, inend);
        root->left = _build(inorder, postorder, prei, inbegin, hash[tmp] - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); i++) {
            hash[inorder[i]] = i;
        }
        int i = postorder.size() - 1;
        return _build(inorder, postorder, i, 0, inorder.size() - 1);
    }
};
class Solution {
public:
    unordered_map<int, int>hash;
    TreeNode* _build(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend) {
        if (inbegin > inend)return nullptr;
        TreeNode* root = new TreeNode(preorder[prei]);
        int tmp = preorder[prei];
        root->left = _build(preorder, inorder, ++prei, inbegin, hash[tmp] - 1);
        root->right = _build(preorder, inorder, prei, hash[tmp] + 1, inend);
        return root;

    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        for (int i = 0; i < inorder.size(); i++) {
            hash[inorder[i]] = i;
        }
        return _build(preorder, inorder, i, 0, inorder.size() - 1);
    }
};
class Solution {
public:
    bool findPath(stack<TreeNode*>& st, TreeNode* root, TreeNode* x) {

        if (root == nullptr)return false;
        st.push(root);
        if (root == x)return true;
        if (findPath(st, root->left, x)) {
            return true;
        }
        if (findPath(st, root->right, x)) {
            return true;
        }
        st.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*>st1;
        stack<TreeNode*>st2;
        findPath(st1, root, p);
        findPath(st2, root, q);
        while (st1.size() != st2.size()) {
            if (st1.size() > st2.size()) {
                st1.pop();
            }
            else {
                st2.pop();
            }
        }
        while (st1.top() != st2.top()) {
            st1.pop();
            st2.pop();
        }
        return st1.top();

    }
};
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>ret;
        if (root == nullptr)return ret;
        queue<TreeNode*>q;
        q.push(root);
        int size = 1;
        while (!q.empty()) {
            vector<int>tmp;
            while (size--) {
                TreeNode* cur = q.front();
                q.pop();
                if (cur->left)q.push(cur->left);
                if (cur->right)q.push(cur->right);
                tmp.push_back(cur->val);
            }
            size = q.size();
            ret.push_back(tmp);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>ret;
        if (root == nullptr)return ret;
        int size = 1;
        queue<TreeNode*>q;
        q.push(root);
        while (!q.empty()) {
            vector<int>tmp;
            while (size--) {
                if (q.front()->left != nullptr)q.push(q.front()->left);
                if (q.front()->right != nullptr)q.push(q.front()->right);
                tmp.push_back(q.front()->val);
                q.pop();
            }
            ret.push_back(tmp);
            size = q.size();
        }
        return ret;
    }
};
class Solution {
public:
    string tree2str(TreeNode* root) {
        string s;
        if (root == nullptr)return s;
        s += to_string(root->val);

        if (root->left || root->right) {
            s += "(";
            s += tree2str(root->left);
            s += ")";
        }


        if (root->right) {
            s += "(";
            s += tree2str(root->right);
            s += ")";
        }
        return s;
    }
};
class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] == '?') {
                for (char x = 'a'; x <= 'z'; x++) {
                    if ((i == 0 || x != s[i - 1]) && (i == n - 1 || x != s[i + 1]))
                    {
                        s[i] = x;
                        break;
                    }
                }

            }
        }
        return s;
    }
};
int main() {
	return 0;
}

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int N = nums.size() + 2;
        int ret = 0;
        for (int i = 1; i <= N; i++)ret ^= i;
        for (auto e : nums)ret ^= e;
        int tmp = 0;
        for (int i = 0; i < 32; i++) {
            if (((ret >> i) & 1) == 1)tmp = i;
        }
        int a = 0, b = 0;
        for (auto e : nums) {
            if (((e >> tmp) & 1) == 1)a ^= e;
        }
        for (int i = 1; i <= N; i++) {
            if (((i >> tmp) & 1) == 1)a ^= i;
        }
        b = ret ^ a;
        return { a,b };
    }
};
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int tmp = 0;
            for (auto e : nums) {
                if (((e >> i) & 1) == 1)tmp++;
            }
            tmp %= 3;
            if (tmp == 1)ret |= (1 << i);
        }
        return ret;
    }
};
class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;
            b = (a & b) << 1;
            a = x;
        }
        return a;
    }
};
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e : nums)ret ^= e;
        for (int i = 0; i <= nums.size(); i++)ret ^= i;
        return ret;
    }
};